Міністерство освіти і науки України Тернопільський національний технічний університет імені Івана Пулюя Кафедра комп’ютерних наук ЛАБОРАТОРНА РОБОТА №3 з дисципліни “Теорія алгоритмів” Тема роботи: : Серіалізм та паралелізм у обчислювальних алгоритмах Тема роботи: Серіалізм та паралелізм у обчислювальних алгоритмах. Мета роботи: Вивчення серіалізму та паралелізму структури обчислювальних алгоритмів на прикладі алгоритмів фільтрації сигналів. Теоретичні відомості При використанні обчислювальних алгоритмів часто суттєвими є не тільки функція, яку він реалізує, але і структура алгоритму. Особливо актуальним є це питання для алгоритмів цифрової фільтрації сигналів, реалізованих на основі спеціалізованих сигнальних процесорів. У цьому випадку з структурою алгоритму пов’язані питання максимальної швидкості обробки, та засобів апаратної реалізації спецпроцера, а отже і його вартості. При розробці алгоритмів цифрової фільтрації використовуються різні форми опису алгоритмів. Найбільш поширеними формами є: Опис у вигляді різницевого рівняння Загальний вигляд рівняння:
, (1) де x-послідовність відліків вхідного сигналу; y-послідовність відліків вихідного сигналу; M, N – цілі числа (
); ai , bi – коефіцієнти. Рівняння (1) містить в собі нерекурсивну частину (сума по N), і рекурсивну частину (сума по M). Алгоритм фільтрації, який описується рівнянням (1) називають рекурсивним а фільтр називають фільтром з нескінченою імпульсною характеристикою. Число М називають порядком рекурсивного фільтру. Якщо вихідний сигнал залежить тільки від вхідного сигналу, тобто
, то алгоритм фільтрації називають нерекурсивним а фільтр - з скінченою імпульсною характеристикою. Число N називають порядком нерекурсивного фільтру. Очевидно, що такий алгоритм вимагає по N+1 комірок пам’яті для зберігання відліків вхідного сигналу і коефіцієнтів аі і M+1 комірок пам’яті для зберігання відліків вихідного сигналу коефіцієнтів bi. 2. Опис у вигляді структурної схеми Позначення основних елементів алгоритму: Елемент Графічне позначення Зауваження  Вузол (комірка пам’яті)  Вузли можуть довільно нумеруватися. Може мати довільну кількість вихідних зв’язків і лише один вхідний.  Зв’язок (помножувач на константу)  Одиничний коефіцієнт на схемі не позначають.  Суматор  Може мати довільну кількість вхідних зв’язків і лише один вихідний.  Одинична затримка  Може мати один вхідний і один вихідний зв’язок.   Елементи на структурній схемі можуть з‘єднуватись послідовно і паралельно. Структурна схема нерекурсивного алгоритму має вигляд рис.1.а. По суті вона являє собою згортку n+1 послідовних відліків вхідного сигналу послідовністю коефіцієнтів а0-аn Структурна схема рекурсивного алгоритму має вигляд рис.1.б. Вона являє собою згортку m послідовних відліків вихідного сигналу з послідовністю коефіцієнтів b1-bm Опис алгоритму у вигляді графа Позначення основних елементів алгоритму на граф-схемі: Елемент Графічне позначення Зауваження  Вузол (комірка пам’яті)  Вузли можуть довільно нумеруватися, можуть мати довільну кількість вхідних і вихідних зв’язків. Всі вхідні зв’язки сумуються (аналог суматора на структурній схемі).  Звязок (помножувач на константу  Одиничний коефіцієнт на схемі не позначають.  Одинична затримка    При використанні структурних схем та графів вводять поняття вхідних і вихідних вузлів Вхідним називається вузол у який не входить жоден зв’язок. Вихідним називається вузол з якого не виходить жоден зв’язок. Для переходу від різницевого рівняння до структурної або граф-схеми необхідно: позначити вузли, які відповідають необхідним коміркам пам‘яті; позначити необхідні ланки затримки та з‘єднати їх з відповіними вузлами; провести всі інші необхідні зв‘язки використовуючи при потребі суматори та ставлячи відповідні помножувачі на коефіцієнти . Опис алгоритму з допомогою системи рівнянь Опис алгоритму системою рівнянь можна реалізувати, записавши у систему рівняння для усіх внутрішніх та вихідних рівня...